1. Field of the Invention
The present invention relates to a circuit synthesis method for an LSI for automatically generating a logic circuit of a register transfer level (RTL) from a behavioral description, and specifically to a high level synthesis method which is especially effective for designing devices which need to be designed within a short period of time such as, for example, ASICs (Application Specific Integrated Circuits).
2. Description of the Related Art
High level synthesis is a technology for automatically generating an RTL logic circuit from a behavioral description which describes only a behavior of calculation processing and does not include information on a hardware structure. High level synthesis is described in detail in Daniel Gajski, Allen Wu, Nikil Dutt and Steve Lin, xe2x80x9cHigh-Level Synthesisxe2x80x9d published by Kluwer Academic Publishers, 1992. High level synthesis is also disclosed in Japanese Laid-Open Publication No. 5-101141. High level synthesis will be described briefly below.  less than Conversion of behavioral description into CDFG greater than 
In high level synthesis, a behavioral description describing only a behavior of calculation processing is analyzed, and then the behavioral description is converted into a model referred to as a control data flowgraph (CDFG) representing the dependency among the calculations, i.e., the execution order of the calculations.
For example, a behavioral description of expression (1) is converted into a CDFG in the following manner.
f={(a*b)+c(b+d))}*exe2x80x83xe2x80x83(1)
A CDFG is a graph in which calculations, inputs and outputs are represented by nodes, and data dependency (i.e., execution order of calculations, inputs and outputs) is represented by directional edges (data dependency edges; e.g., arrows). For example, in FIG. 1, which illustrates a CDFG 100 corresponding to the behavioral description of expression (1), a data dependency edge 14 indicates that an addition 5 is performed after a first multiplication 4 is performed. In the CDFG 100, inputs xe2x80x9caxe2x80x9d, xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d and xe2x80x9cexe2x80x9d are respectively represented by reference numerals 28 through 32, and an output xe2x80x9cfxe2x80x9d is represented by reference numeral 33. As mentioned above, the first multiplication (xe2x80x9c*xe2x80x9d) is represented by reference numeral 4, and first, second and third additions (xe2x80x9c+xe2x80x9d) are respectively represented by reference numerals 5, 6 and 7. A second multiplication (xe2x80x9c*xe2x80x9d) is represented by reference numeral 8. In this specification, symbol xe2x80x9c*xe2x80x9d indicates multiplication.
A data dependency edge from the input xe2x80x9caxe2x80x9d 28 to the first multiplication 4 is represented by reference numeral 11. A data dependency edge from the input xe2x80x9cbxe2x80x9d 29 to the first multiplication 4 is represented by reference numeral 12. A data dependency edge from the input xe2x80x9cbxe2x80x9d 29 to the second addition 6 is represented by reference numeral 13. A data dependency edge from the first multiplication 4 to the first addition 5 is represented by reference numeral 14. A data dependency edge from the input xe2x80x9ccxe2x80x9d 30 to the first addition 5 is represented by reference numeral 15. A data dependency edge from the input xe2x80x9cdxe2x80x9d 31 to the second addition 6 is represented by reference numeral 16. A data dependency edge from the first addition 5 to the third addition 7 is represented by reference numeral 17. A data dependency edge from the second addition 6 to the third addition 7 is represented by reference numeral 18. A data dependency edge from the third addition 7 to the second multiplication 8 is represented by reference numeral 19. A data dependency edge from the input xe2x80x9cexe2x80x9d 32 to the second multiplication 8 is represented by reference numeral 20. A data dependency edge from the second multiplication 8 to the output xe2x80x9cfxe2x80x9d 33 is represented by reference numeral 21.
 less than Scheduling greater than 
After the behavioral description of expression (1) is converted into the CDFG 100 (FIG. 1), scheduling is performed. Scheduling is processing for assigning the calculations, inputs and the outputs to time slots. (The CDFG 100 (FIG. 1) includes only one output.) Each time slot corresponds to a state of a finite state machine and is referred to as a scheduling step.
FIG. 2 shows a scheduling result 110 obtained as a result of scheduling the CDFG 100 (FIG. 1). In FIG. 2, the input xe2x80x9caxe2x80x9d 28 and the input xe2x80x9cbxe2x80x9d 29 are scheduled in scheduling step 0. The first multiplication 4, the input xe2x80x9ccxe2x80x9d 30, the input xe2x80x9cdxe2x80x9d 31, the first addition 5 and the second addition 6 are scheduled in scheduling step 1. The third addition 7, the input xe2x80x9cexe2x80x9d 32 and the second multiplication 8 are scheduled in scheduling step 2. Only the output xe2x80x9cfxe2x80x9d 33 is scheduled in scheduling step 3.
The same type of calculations scheduled in different scheduling steps can share one calculation device. In FIG. 2, the first addition 5 and the third addition 7 are respectively scheduled in scheduling steps 1 and 2, and therefore can share one calculation device. The second addition 6 and the third addition 7 are also respectively scheduled in scheduling steps 1 and 2, and therefore can share one calculation device. The first multiplication 4 and the second multiplication 8 are respectively scheduled in scheduling steps 1 and 2, and therefore can share one calculation device. By scheduling, each of the calculations is assigned to an appropriate scheduling step so as to minimize the cost of the hardware.
In the scheduling result 110 shown in FIG. 2, the data dependency edges 11, 12 and 13 cross the clock boundary between scheduling steps 0 and 1. The data dependency edges 17 and 18 cross the clock boundary between scheduling steps 1 and 2. The data dependency edge 21 crosses the clock boundary between scheduling steps 2 and 3.
 less than Allocation greater than 
Allocation is processing for allocating calculation devices, registers, and input and output pins required to execute the scheduled CDFG: and assigning the calculations of the CDFG to the calculation devices, assigning the data dependency edges crossing the clock boundaries between two adjacent scheduling steps to the registers, and assigning the inputs and outputs to the input and output pins. (Only one output is necessary for the CDFG 100 in FIG. 1.)
FIGS. 3, 4 and 5 show allocation procedures 120, 121 and 122 performed on the CDFG 100 (FIG. 1) scheduled as shown in FIG. 2. FIG. 3 shows an allocation procedure 120 for the calculation devices; FIG. 4 shows an allocation procedure 121 for the registers; and FIG. 5 shows an allocation procedure 122 for the inputs and the output.
By the allocation procedure 120 for the calculation devices shown in FIG. 3, one multiplier 1 (xe2x80x9cmult 1xe2x80x9d), and first and second adders 2 and 3 (xe2x80x9cadder 1xe2x80x9d and xe2x80x9cadder 2xe2x80x9d) are allocated. The first and second multiplications 4 and 8 scheduled in different scheduling steps are assigned to the multiplier 1. The first and third additions 5 and 7 scheduled in different scheduling steps are assigned to the first adder 2. The second adder 6 scheduled in scheduling step 1 is assigned to the second adder 3.
By the allocation procedure 121 for the registers shown in FIG. 4, a first register 41 (xe2x80x9creg 1xe2x80x9d) and a second register 42 (xe2x80x9creg 2xe2x80x9d) are allocated. One of the data dependency edges crossing the clock boundary between scheduling steps 0 and 1 (data dependency edge 11) and one of the data dependency edges crossing the clock boundary between scheduling steps 1 and 2 (data dependency edge 17) are assigned to the first register 41. The other data dependency edge crossing the clock boundary between scheduling steps 0 and 1 (data dependency edge 13), the other data dependency edge crossing the clock boundary between scheduling steps 1 and 2 (data dependency edge 18), and the data dependency edge 21 crossing the clock boundary between scheduling steps 2 and 3 are assigned to the second register 42.
By the allocation procedure 122 for the inputs and output shown in FIG. 5, five input pins xe2x80x9caxe2x80x9d 22, xe2x80x9cbxe2x80x9d 23, xe2x80x9ccxe2x80x9d 24, xe2x80x9cdxe2x80x9d 25, and xe2x80x9cexe2x80x9d 26, and one output pin xe2x80x9cfxe2x80x9d 27 are allocated. The input xe2x80x9caxe2x80x9d 28 is assigned to the input pin xe2x80x9caxe2x80x9d 22, the input xe2x80x9cbxe2x80x9d 29 is assigned to the input pin xe2x80x9cbxe2x80x9d 23, the input xe2x80x9ccxe2x80x9d 30 is assigned to the input pin xe2x80x9ccxe2x80x9d 24, the input xe2x80x9cdxe2x80x9d 31 is assigned to the input pin xe2x80x9cdxe2x80x9d 25, and the input xe2x80x9cexe2x80x9d 32 is assigned to the input pin xe2x80x9cexe2x80x9d 26. The output xe2x80x9cfxe2x80x9d 33 is assigned to the output pin xe2x80x9cfxe2x80x9d 27.
 less than Data path generation greater than 
Data path generation is processing for generating circuit paths corresponding to the data dependency edges in the CDFG. FIG. 6 shows an exemplary data path generation result 130 obtained as a result of the data path generation performed on the CDFG 100 (FIG. 1).
For the calculation devices, registers or the like which are shared, a multiplexer is allocated for selecting data to be input to the calculation devices, registers or the like. In FIG. 6, a first multiplexer 43 (xe2x80x9cmux 1xe2x80x9d) is allocated for the first register 41, and a second multiplexer 44 (xe2x80x9cmux 2xe2x80x9d) is allocated for the second register 42. A third multiplexer 45 (xe2x80x9cmux 3xe2x80x9d)and a fourth multiplexer 46 (xe2x80x9cmux 4xe2x80x9d) are allocated for the multiplier 1. A fifth multiplexer 47 (xe2x80x9cmux 5xe2x80x9d) and a sixth multiplexer 48 (xe2x80x9cmux 6xe2x80x9d) are allocated for the first adder 2.
A data path which corresponds to a path from the input xe2x80x9caxe2x80x9d 28 through the data dependency edge 11 to the first multiplication 4 is generated by first generating a path from the input pin xe2x80x9caxe2x80x9d 22 through the first multiplexer 43 to the first register 41 and then generating a path from the first register 41 to the multiplier 1. Other data paths are generated in a similar manner.
 less than Controller generation greater than 
Controller generation is processing for generating a controller for controlling the calculation devices, registers and multiplexers allocated by the allocation and the data path generation.
FIG. 7 shows an exemplary controller generation result 140 obtained as a result of generating a controller 50. The controller 50 controls the first and second multiplexers 43 and 44, the first and second registers 41 and 42, the third and fourth multiplexers 45 and 46, and fifth and sixth multiplexers 47 and 48.
As described above, in high level synthesis, a plurality of calculations connected by data dependency edges can be scheduled in one scheduling step and can share one calculation device. In such high level synthesis, a feedback loop formed of a combination of at least two portions of true paths and at least one calculation device may be generated during the data path generation. The feedback loop is a false path which is not required for operating the circuit. A true path is a data path which becomes entirely active in either one of scheduling steps (i.e., either one of states of the finite state machine); and a false path is a data path which does not become entirely active in either one of scheduling steps.
FIG. 8 shows an exemplary data path generation result 150 obtained for the CDFG 100 (FIG. 1). In the data path generation result 150, a feedback loop 49 from the first multiplier 1xe2x80x94the first adder 2xe2x80x94the third multiplexer 45 to the first multiplier 1 is a false path. The feedback loop 49 is formed by combining a portion of each of the following two true paths. One true path is: the first register 41xe2x80x94the third multiplexer 45xe2x80x94the multiplier 1xe2x80x94the fifth multiplexer 47xe2x80x94the first adder 2xe2x80x94the first multiplexer 43xe2x80x94the first register 41. The other true path is: the first register 41xe2x80x94the fifth multiplexer 47xe2x80x94the first adder 2xe2x80x94the third multiplexer 45xe2x80x94the multiplier 1xe2x80x94the first multiplexer 43xe2x80x94the first register 41. A portion from the first true path: the multiplier 1xe2x80x94the fifth multiplexer 47xe2x80x94the first adder 2 is combined with a portion from the second true path: the first adder 2xe2x80x94the third multiplexer 45xe2x80x94the multiplier 1. Thus, the feedback loop 49 is formed.
A feedback loop is a false path. However, in an actual situation including a path delay, the feedback loop may undesirably become entirely active temporarily before the signal is stabilized. When this occurs, oscillation or the like is caused in the RTL logic circuit and the RTL logic circuit is destabilized.
In addition, when the RTL logic circuit includes a feedback loop, the static timing analysis for the logic synthesis becomes difficult.
According to one aspect of the invention, a circuit synthesis method includes the steps of converting a behavioral description describing a behavior of calculation processing into a control data flowgraph; assigning a plurality of calculations, at least one input and at least one output in the control data flowgraph into a plurality of prescribed time slots; assigning the plurality of calculations, a plurality of data dependency edges, the at least one input and the at least one output respectively to a plurality of calculation devices, at least one register, at least one input pin and at least one output pin; generating a plurality of paths corresponding to the plurality of data dependency edges; and detecting a feedback loop formed of at least two of the plurality of paths and at least one of the plurality of calculation devices; and re-assigning one calculation, which has been assigned to a first calculation device included in the feedback loop, to a second calculation device among the plurality of calculation devices, so as to delete the feedback loop.
In one embodiment of the invention, the step of re-assigning includes the step of assigning the one calculation to the second calculation device when the second calculation device is confirmed to be capable of executing the one calculation and not to perform another calculation within a first prescribed time slot among the plurality of time slots in which the one calculation is performed.
In one embodiment of the invention, the circuit synthesis method further includes the step of, when the feedback loop is not deleted by assigning the one calculation to the second calculation device, allocating a third calculation device and assigning the one calculation to the third calculation device so as to delete the feedback loop.
In one embodiment of the invention, the step of allocating the third calculation device includes the step of allocating the third calculation device by forming a replication of the first calculation device.
In one embodiment of the invention, the step of allocating the third calculation device by forming a replication of the first calculation device includes the step of forming a replication of the first calculation device as a calculation device having a minimum area among the at least two calculation devices included in the feedback loop.
According to another aspect of the invention, a recording medium having a program written thereon for causing a computer to execute circuit synthesis is provided. The synthesis is performed by a method including the steps of converting a behavioral description describing a behavior of calculation processing into a control data flowgraph; assigning a plurality of calculations, at least one input and at least one output in the control data flowgraph into a plurality of prescribed time slots; assigning the plurality of calculations, a plurality of data dependency edges, the at least one input and the at least one output respectively to a plurality of calculation devices, at least one register, at least one input pin and at least one output pin; generating a plurality of paths corresponding to the plurality of data dependency edges; detecting a feedback loop formed of at least two of the plurality of paths and at least one of the plurality of calculation devices; and re-assigning one calculation, which has been assigned to a first calculation device included in the feedback loop, to a second calculation device among the plurality of calculation devices, so as to delete the feedback loop.
Thus, the invention described herein makes possible the advantages of providing a circuit synthesis method for preventing an RTL logic circuit generated from a behavioral description from being destabilizing due to oscillation or the like and for allowing automatic design of an RTL logic circuit for which static timing analysis is relatively easy.
These and other advantages of the present invention will become apparent to those skilled in the art upon reading and understanding the following detailed description with reference to the accompanying figures.